#include <stdlib.h>
#include <string.h>

#define MaxLen 2000

//ZArr[i]表示从i出发到结尾的字符串与总字符串的前缀最大匹配长度
int ZArr[MaxLen];

//EArr[i]表示从i出发到结尾的字符串与另一个字符串B的前缀最大匹配长度
int EArr[MaxLen];

int Min(int a, int b)
{
    return a < b ? a : b;
}

//获取Z数组，与Manacher相似，只是关键点从「2*c-i」变成了「i-c」
void GetZArr(const char* str)
{
    int strLen = strlen(str);
    ZArr[0] = strLen;
    int c = 1, r = 1;
    for (int i = 0; i < strLen; ++i)
    {
        ZArr[i] = i < r ? Min(r - i, ZArr[i - c]) : 0;
        while (i + ZArr[i] < strLen)
        {
            if(str[i + ZArr[i]] == str[ZArr[i]])
                ++ZArr[i];
            else break;
        }
        if(i + ZArr[i] > r)
        {
            r = i + ZArr[i];
            c = i;
        }
    }
}

//获取从A相对于B字符串的E数组
void GetEArr(const char* a, const char* b)
{
    //获取B字符串的Z数组
    GetZArr(b);
    int c = 0, r = 0;
    int aLen = strlen(a), bLen = strlen(b);
    for (int i = 0; i < aLen; ++i)
    {
        EArr[i] = i < r ? Min(r - i, ZArr[i - c]) : 0;
        while (i + EArr[i] < aLen && EArr[i] < bLen)
        {
            if(a[i + EArr[i]] == b[EArr[i]])
                ++EArr[i];
            else break;
        }
        if(i + EArr[i] > r)
        {
            r = i + EArr[i];
            c = i;
        }
    }
}